package heapsort

func HeapSort(arr []int) []int {
	length := len(arr)
	heapify(arr)
	for i := length - 1; i > 0; i-- {
		arr[0], arr[i] = arr[i], arr[0]
		adjustHeap(arr, 0, i)
	}
	return arr
}

func heapify(arr []int) {
	length := len(arr)
	for height := length/2 - 1; height >= 0; height-- {
		adjustHeap(arr, height, length)
	}
}

func adjustHeap(arr []int, i, length int) {
	temp := arr[i]
	for k := 2*i + 1; k < length; k = 2*k + 1 {
		if k+1 < length && arr[k] < arr[k+1] {
			k++
		}
		if arr[k] > temp {
			arr[i] = arr[k]
			i = k
		} else {
			break
		}
	}
	arr[i] = temp
}
